import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-04-23
 * Time: 10:21
 */
public class Sort {

    /**
     * 时间复杂度O(n^2)
     * 空间复杂度O(1)
     * 稳定的排序
     * @param arr
     */
    //插入排序
    public static void insetSort(int[] arr) {
        for(int i = 1 ; i < arr.length ; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (;  j>= 0 ; j--) {
                if(arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                }else {
                    arr[j + 1] = tmp;
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    /**
     * 不稳定的排序
     * 时间复杂度:n^1.3 - n^1.5
     * 空间复杂度O(1)
     * @param arr
     */
    //希尔排序
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap > 1){
            gap /= 2;
            shell(arr, gap);
        }
    }

    private static void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for( ; j >= 0 ; j -= gap){
                if(arr[j] > tmp){
                    arr[j + gap] = arr[j];
                }else {
                    arr[j + gap] = tmp;
                    break;
                }
            }
            arr[j + gap] = tmp;
        }
    }

    /**
     * 时间复杂度O(n^2)
     * 和数据是否有序无关
     * 空间复杂度O(1)
     * 稳定性:不稳定
     * @param arr
     */
    //选择排序
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr,i , minIndex);
        }
    }

    private static void swap(int[] arr, int i , int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //选择排序(改进)
    public static void selectSort2(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
                swap(arr, left, minIndex);

                //最大值如果正好是left下标， 此时把最大值换到了minIndex的位置
                if (maxIndex == left) {
                    maxIndex = minIndex;
                }
                swap(arr, right, maxIndex);

                left++;
                right--;

        }
    }

    /**
     * 时间复杂度：O(n*logN)
     * 空间复杂度: O(1)
     * 稳定性：不稳定
     * @param arr
     */
    //堆排序
    public static void heapSort(int[] arr) {
        creatHeap(arr);
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr , 0, end);
            siftDown(arr , 0, end);
            end--;
        }
    }

    //创建大根堆
    private static void creatHeap(int[] arr) {
        for(int parent = (arr.length - 1) / 2 ; parent >= 0; parent--) {
            siftDown(arr, parent , arr.length);
        }
    }

    /**
     *
     * @param arr
     * @param parent 每颗子树调整的根节点
     * @param length 每颗子树调整的结束节点
     */
    //向下调整
    private static void siftDown(int[] arr, int parent , int length) {
        int child = 2 * parent + 1;
        while(child < length) {
            if(child + 1 < length && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                swap(arr, parent , child);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 时间复杂度：在没有优化的情况下，也就是 没有下方的boolen 和 - i的操作，时间复杂度会达到O(N^2)
     * 优化以后复杂度可能会达到O(N)
     * 空间复杂度： O(1)
     * 稳定性：稳定的排序
     * @param arr
     */
    //冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j , j + 1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

    /**
     * 时间复杂度：
     *          最坏情况：当数据为1 2 3 4 5 6 7 ....有序的情况下 是O(N^2)
     *                         9 8 7 6 5 4 3...
     *                         可以用三数取中法优化
     *          最好的情况： O(N*logN)
     * 空间复杂度：
     *          最坏情况O(N)
     *          最好的情况O(logN)
     * 稳定性：
     *         不稳定
     * @param arr
     */

    //快速排序
    public static void quickSort(int[] arr) {
        //quick(arr , 0 , arr.length - 1);
        quickStack(arr, 0, arr.length - 1);
    }

    //非递归写法
    public static void quickStack(int[] arr, int start, int end) {
        Deque<Integer> stack = new ArrayDeque<>();
        int pivot = partition(arr, start, end);
        if(pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }

        if(pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }

        while(!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(arr, start, end);

            if(pivot > start + 1) {
                stack.push(start);
                stack.push(pivot - 1);
            }

            if(pivot < end - 1) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    //递归写法
    private static void quick(int[] arr, int start , int end) {
        if(start >= end){
            return;
        }

        //优化(当长度小于一定长度后用选择排序，长度越小越趋于)
        if(end - start + 1 <= 7) {
            insetSortRange(arr, start, end);
            return;
        }

        //优化(三数取中法)
        int midIndex = getMiddleNum(arr, start , end);
        swap(arr, start, midIndex);

        //int pivot = partition(arr , start , end);
        //int pivot = partition2(arr, start, end);
        int pivot = partition3(arr, start , end);
        quick(arr, start , pivot - 1);
        quick(arr, pivot + 1, end);
    }

    private static void insetSortRange(int[] arr,int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for(; j >= start ; j--) {
                if(arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                }else {
                    arr[j + 1] = tmp;
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    private static int getMiddleNum(int[] arr, int left , int right) {
        int mid = (left + right) / 2;
        if(arr[left] < arr[right]) {
            if(arr[mid] < arr[left]) {
                return left;
            }else if(arr[mid] > arr[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(arr[mid] > arr[left]) {
                return left;
            }else if(arr[mid] < arr[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }

    //找分割关键数(霍尔法)
    private static int partition(int[] arr, int left , int right) {
        int tmp = arr[left];
        int tmpLeft = left;
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, left , tmpLeft);
        return left;
    }

    //找分割关键数(前后指针法)
    public static int partition2(int[] arr, int left , int right) {
        int prev = left;
        int cur = left + 1;
        while(cur <= right) {
            if(arr[cur] < arr[left] && arr[++prev] != arr[cur]) {
                swap(arr, prev, cur);
            }
            cur++;
        }
        swap(arr,prev,left);
        return prev;
    }

    //找分割关键数(挖坑法)默认方法
    public static int partition3(int[] arr, int left , int right) {
        int tmp = arr[left];
        while (left < right) {
            if (left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            if (left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

    /**
     * 时间复杂度：O(N*logN)
     * 空间复杂度：0(N)
     * 稳定性：稳定的排序
     * @param arr
     */
    //归并排序
    public static void mergeSort(int[] arr) {
        mergeSortChild(arr, 0, arr.length - 1);
    }

    //递归写法
    private static void mergeSortChild(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }

        //分解
        int mid = (left + right) / 2;
        mergeSortChild(arr, left, mid);
        mergeSortChild(arr, mid + 1, right);
        //分解完毕

        //合并
        merge(arr, left , mid, right);
    }

    //非递归写法
    public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while(gap < arr.length) {
            for (int i = 0; i < arr.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= arr.length) {
                    mid = arr.length - 1;
                }
                int right = mid + gap;
                if(right >= arr.length) {
                    right = arr.length - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int k = 0;
        int[] tmp = new int[right - left + 1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        while (s1 <= mid && s2 <= right) {
            if(arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            }else {
                tmp[k++] = arr[s2++];
            }
        }

        while(s1 <= mid) {
            tmp[k++] = arr[s1++];
        }

        while(s2 <= right) {
            tmp[k++] = arr[s2++];
        }

        for (int i = 0; i < k; i++) {
            arr[i + left] = tmp[i];
        }
    }

    //计数排序
    public static void countSort(int[] arr) {
        //先找最大值，最小值来确定数组的大小
        int maxVal = arr[0];
        int minVal = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > maxVal) {
                maxVal = arr[i];
            }
            if(arr[i] < minVal) {
                minVal = arr[i];
            }
        }
        int len = maxVal - minVal + 1;
        int[] count = new int[len];

        //遍历数组arr，把每个元素放大对应的计数数组中进行计数
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i];
            count[index - minVal]++;
        }

        //依次遍历计数数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                arr[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }
}
